package pro.softzhang.algo.lc700;


public class LC790_DominoAndTrominoTiling {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int numTilings(int n) {
            if (n == 1) return 1;
            long[] dp = new long[n + 1];
            dp[0] = dp[1] = 1;
            dp[2] = 2;
            for(int i = 3; i <= n; i++) {
                dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % ((int)1e9 + 7);
            }
            return (int)dp[n];
        }
    }
}
